package 力扣竞赛.第29场双周赛20200627;

import java.util.Arrays;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/7/5 20:43
 */
public class No1494_并行课程 {
    public static void main(String[] args) {
        Solution1494 solution1494 = new Solution1494();
        int n = 5;
        int[][] dependencies = new int[][]{{2, 1}, {3, 1}, {4, 1}, {1, 5}};
        int k = 2;
        int res = solution1494.minNumberOfSemesters(n, dependencies, k);
        System.out.println(res);
    }
}
class Solution1494 {
    public int minNumberOfSemesters(int n, int[][] dependencies, int k) {
        //修第i课程的前驱课程
        int[] pre = new int[n];
        for (int[] d : dependencies) {
            //索引化
            d[0]--;
            d[1]--;
            pre[d[1]] = pre[d[1]] | (1 << d[0]); // 如 1的前驱课程 01110 从右往左数为 2,3,4课程
        }
        int[] dp = new int[1 << n]; //dp[n] 代表学到n状态下最少需要多少学期
        Arrays.fill(dp, 34539); //随便搞数,因可能没有前驱课程,0会冲突!
        dp[0] = 0;//没有0号课程
        for (int state = 0; state < 1 << n; state++) {
            int next = 0;
            for (int a1 = 0; a1 < n; a1++) {
                if ((pre[a1] & state) == pre[a1]) {//当前状态和前驱状态相同,可以进行下一级状态操作
                    next = next | pre[a1] | (1 << a1);
                }
            }
            next = next & ~state;
            //枚举子集 如01110子集为 01100,01000
            for (int sub = next; sub > 0; sub = (sub - 1) & next) {
                if (Integer.bitCount(sub) <= k) {
                    //这个课和下个课一起搞
                    dp[state | sub] = Math.min(dp[state | sub], dp[state] + 1);
                }
            }
        }
        return dp[(1 << n) - 1];
    }

}



    ////状态压缩动态规划参考代码
    //public int maxStudents(char[][] seats) {
    //    int m = seats.length;
    //    int n = seats[0].length;
    //    int all = 1 << n;
    //    int[][] dp = new int[m + 1][all];
    //    for (int i = 1; i <= m; i++) {
    //        for (int j = 0; j < all; j++) {
    //            //检查行状态自身与位置是否符合
    //            if (!isOK_03(seats, i - 1, j)) continue;
    //            int count = Integer.bitCount(j);
    //            for (int k = 0; k < all; k++) {
    //                //上一排左上右上不能有学生??
    //                if ((j & (k << 1)) != 0 || (j & (k >> 1)) != 0) continue;
    //                dp[i][j] = Math.max(dp[i][j], dp[i - 1][k] + count);
    //            }
    //        }
    //    }
    //    int ans = 0;
    //    for (int i : dp[m]) {
    //        ans = Math.max(ans, i);
    //    }
    //    return ans;
    //}
    //
    //private boolean isOK_03(char[][] seats, int index, int cur) {
    //    //判断当前行位置左右是否符合
    //    if ((cur & (cur << 1)) != 0 && (cur & (cur >> 1)) != 0) return false;
    //    int n = seats[index].length;
    //    //检查该状态是否符合seats的位置,有坏椅子
    //    for (int i = 0; i < n; i++) {
    //        int bit = 1 << i;
    //        //找到#,把1过去跟#(实际就是0比较,如果cur在该位置安排了学生,则说明结果不是0,返回false)
    //        if (seats[index][n-i-1] == '#' && (cur & bit) != 0) return false;
    //    }
    //    return true;
    //}
